package leetcode每日一题.leetcode20212;

/**
 * 1. 问题描述
 *      给你一个长度为n的整数数组，请你判断在最多改变1个元素的情况下，该数组能否变成一个非递减数列。
 *      我们是这样定义一个非递减数列的：对于数组中所有的i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。
 *
 * 2. 算法分析
 *      注释中有详细分析
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class Q006_非递减序列 {
    public boolean checkPossibility(int[] nums) {
        int n = nums.length;
        // 数组的个数小于等于2一定成立
        if(n <= 2) {
            return true;
        }
        // 当数组的个数大于等于3的时候
        // 分析：
        // 如果数组中nums[i] < nums[i-1] 的个数大于等于2，此时需要调整的元素个数一定不能少于2次
        // 所以我们需要设置一个变量记录，如果大于等于2，直接返回false
        // 下面我们只需要考虑数组中存在一个上述的情况，如果没有说明当前数组本身就是递增的，直接返回true
        // 对于只有一个的这种情况就不一定成立了，我们先通过一个例子来看 [3,4,2,3]，此时数组中只有 nums[1] > nums[2]
        // 假设我们现在想要将数组变为单调递增，我们只能将nums[1]调整到至多nums[2]，此处如果按照贪心的思路来看，nums[1]
        // 越大，nums[1]之前的元素小于等于调整后的nums[1]的可能性就越大，假设nums[1]调整为nums[2],此时数组变为[3,2,2,3]
        // 发现任然不为单调数组，因为nums[1]之前的元素nums[0] > nums[2],此时如果成立，必须要求nums[0] <= nums[2]
        // nums[2]之后一定是单调增的，因为数组中只有一个下降的相邻子数组，所以不需要考虑
        // 由此,抽象出上述：假设nums[i] < nums[i-1](只此一处)，我们将nums[i-1]调整为nums[i]
        // 判断nums[i-2]是否小于等于nums[i],如果下小于等于，则可以调整，否则无法调整
        int count = 0; // 记录下降的个数
        for(int i = 1; i < n; i++) {
            if(nums[i-1] > nums[i]) {
                count++;
            }
            // 判断
            if(count > 1) {
                return false;
            }
            // 判断count=1
            if(count == 1) {
                if(i > 1 && i < n-1 && nums[i-2] > nums[i] && nums[i-1] > nums[i+1]) {
                    return false;
                }
            }
        }
        return true;
    }
}
